home *** CD-ROM | disk | FTP | other *** search
/ Speccy ClassiX 1998 / Speccy ClassiX 98.iso / amiga_system / the_aminet / dev / gcc / ixemulsrc.lha / ixemul-41.4 / network / page.c < prev    next >
C/C++ Source or Header  |  1995-05-18  |  23KB  |  906 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)page.c    5.13 (Berkeley) 6/17/91";
  39. #endif /* LIBC_SCCS and not lint */
  40. #undef DEBUG
  41. /******************************************************************************
  42. PACKAGE:  hashing
  43.  
  44. DESCRIPTION: 
  45.     Page manipulation for hashing package.
  46.  
  47. ROUTINES: 
  48.     External
  49.     __get_page
  50.     __add_ovflpage
  51.     Internal
  52.     overflow_page
  53.     open_temp
  54. ******************************************************************************/
  55.  
  56. #include <sys/param.h>
  57. #include <fcntl.h>
  58. #include <signal.h>
  59. #include <assert.h>
  60. #include <errno.h>
  61. #include <db.h>
  62. #include <stdio.h>
  63. #include <stdlib.h>
  64. #include <string.h>
  65. #include <unistd.h>
  66. #include "hash.h"
  67. #include "page.h"
  68.  
  69. /* Externals */
  70. /* buf.c */
  71. extern BUFHEAD    *__get_buf();
  72. extern void __reclaim_buf();
  73.  
  74. /* big.c */
  75. extern int __big_split();
  76. extern int __big_insert();
  77. extern int __big_delete();
  78. extern int __find_bigpair();
  79.  
  80. /* dynahash.c */
  81. extern    u_int    __call_hash();
  82. extern    int    __expand_table();
  83.  
  84. /* my externals */
  85. extern int __get_page();
  86. extern BUFHEAD *__add_ovflpage();
  87. extern int __split_page();
  88. extern int __addel();
  89.  
  90. /* my internals */
  91. static u_short overflow_page();
  92. static int open_temp();
  93. static int ugly_split();
  94. static void squeeze_key();
  95. static void putpair();
  96. static u_long *fetch_bitmap();
  97.  
  98. #ifdef HASH_STATISTICS
  99. extern long hash_accesses, hash_collisions, hash_expansions, hash_overflows;
  100. #endif
  101. #define    PAGE_INIT(P)                    \
  102. {                            \
  103.     ((u_short *)P)[0] = 0;                \
  104.     ((u_short *)P)[1] = hashp->BSIZE - 3 * sizeof(u_short);    \
  105.     ((u_short *)P)[2] = hashp->BSIZE;            \
  106. }
  107.  
  108. /*
  109.     This is called AFTER we have verified that there is room on the
  110.     page for the pair (PAIRFITS has returned true) so we go right
  111.     ahead and start moving stuff on.
  112. */
  113. static void
  114. putpair(p, key, val)
  115. char *p;
  116. DBT *key;
  117. DBT *val;
  118. {
  119.     register u_short n;
  120.     register u_short off;
  121.     register u_short *bp = (u_short *) p;
  122.  
  123. /* enter the key first */
  124.     n = bp[0];
  125.  
  126.     off = OFFSET(bp) - key->size;
  127.     bcopy( key->data, p+off, key->size );
  128.     bp[++n] = off;
  129.  
  130. /* now the data */
  131.     off -= val->size;
  132.     bcopy(val->data,  p + off, val->size);
  133.     bp[++n] = off;
  134.  
  135. /* adjust page info */
  136.     bp[0] = n;
  137.     bp[n+1] = off - ((n+3)*sizeof(u_short));
  138.     bp[n+2] = off;
  139.     return;
  140. }
  141. /*
  142.     0 OK
  143.     -1 error
  144. */
  145. extern int
  146. __delpair(bufp, ndx)
  147. BUFHEAD *bufp;
  148. register int ndx;
  149. {
  150.     register u_short *bp = (u_short *) bufp->page;
  151.     register int n = bp[0];
  152.     register u_short newoff;
  153.     u_short pairlen;
  154.  
  155.     if ( bp[ndx+1] < REAL_KEY ) return ( __big_delete ( bufp, ndx ) );
  156.     if ( ndx != 1 ) newoff = bp[ndx-1];
  157.     else newoff = hashp->BSIZE;
  158.     pairlen = newoff - bp[ndx+1];
  159.  
  160.     if ( ndx != (n-1) ) {
  161.         /* Hard Case -- need to shuffle keys */
  162.         register int i;
  163.         register char *src = bufp->page + (int)OFFSET(bp);
  164.         register char *dst = src + (int)pairlen;
  165.         bcopy ( src, dst, bp[ndx+1] - OFFSET(bp) );
  166.  
  167.         /* Now adjust the pointers */
  168.         for ( i = ndx+2; i <= n; i += 2 ) {
  169.             if ( bp[i+1]  == OVFLPAGE ) {
  170.             bp[i-2] = bp[i];
  171.             bp[i-1] = bp[i+1];
  172.             } else {
  173.             bp[i-2] = bp[i] + pairlen;
  174.             bp[i-1] = bp[i+1] + pairlen;
  175.             }
  176.         }
  177.     }
  178.  
  179.     /* Finally adjust the page data */
  180.     bp[n] = OFFSET(bp) + pairlen;
  181.     bp[n-1] = bp[n+1] + pairlen + 2 * sizeof(u_short);
  182.     bp[0] = n-2;
  183.     hashp->NKEYS--;
  184.  
  185.     bufp->flags |= BUF_MOD;
  186.     return (0);
  187. }
  188. /*
  189.     -1 ==> Error
  190.     0 ==> OK
  191. */
  192. extern int
  193. __split_page(obucket, nbucket)
  194. u_int obucket;
  195. u_int nbucket;
  196. {
  197.     DBT key;
  198.     DBT val;
  199.  
  200.     register BUFHEAD *new_bufp;
  201.     register BUFHEAD *old_bufp;
  202.     register u_short *ino;
  203.     register char    *np;
  204.     int n;
  205.     int ndx;
  206.     int retval;
  207.     char    *op;
  208.  
  209.     u_short copyto = (u_short)hashp->BSIZE;
  210.     u_short diff;
  211.     u_short off = (u_short)hashp->BSIZE;
  212.     u_short moved;
  213.  
  214.     old_bufp = __get_buf ( obucket, NULL, 0 );
  215.     new_bufp = __get_buf ( nbucket, NULL, 0 );
  216.  
  217.     old_bufp->flags |= (BUF_MOD|BUF_PIN);
  218.     new_bufp->flags |= (BUF_MOD|BUF_PIN);
  219.  
  220.     ino = (u_short *)(op = old_bufp->page);
  221.     np = new_bufp->page;
  222.  
  223.     moved = 0;
  224.  
  225.     for (n = 1, ndx = 1; n < ino[0]; n+=2) {
  226.         if ( ino[n+1] < REAL_KEY ) {
  227.             retval = ugly_split( obucket, old_bufp, new_bufp, 
  228.                      copyto, moved );
  229.             old_bufp->flags &= ~BUF_PIN;
  230.             new_bufp->flags &= ~BUF_PIN;
  231.             return(retval);
  232.             
  233.         }
  234.         key.data = (u_char *)op + ino[n]; 
  235.         key.size = off - ino[n];
  236.  
  237.         if ( __call_hash ( key.data, key.size ) == obucket ) {
  238.             /* Don't switch page */
  239.             diff = copyto - off;
  240.             if ( diff ) {
  241.             copyto = ino[n+1] + diff;
  242.             bcopy ( op + ino[n+1], op + copyto,  off-ino[n+1]);
  243.             ino[ndx] = copyto + ino[n] - ino[n+1];
  244.             ino[ndx+1] = copyto;
  245.             } else copyto = ino[n+1];
  246.             ndx += 2;
  247.         } else {
  248.             /* Switch page */
  249.             val.data = (u_char *)op + ino[n+1];
  250.             val.size = ino[n] - ino[n+1];
  251.             putpair( np, &key, &val);
  252.             moved +=2;
  253.         }
  254.  
  255.         off = ino[n+1];
  256.     }
  257.  
  258.     /* Now clean up the page */
  259.     ino[0] -= moved;
  260.     FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0]+3);
  261.     OFFSET(ino) = copyto;
  262.  
  263. #ifdef DEBUG3
  264.     fprintf(stderr, "split %d/%d\n", 
  265.            ((u_short *) np)[0] / 2,
  266.            ((u_short *) op)[0] / 2);
  267. #endif
  268.     /* unpin both pages */
  269.     old_bufp->flags &= ~BUF_PIN;
  270.     new_bufp->flags &= ~BUF_PIN;
  271.     return(0);
  272. }
  273. /*
  274.     0 ==> success
  275.     -1 ==> failure
  276.  
  277.     Called when we encounter an overflow or big key/data page during 
  278.     split handling.
  279.     This is special cased since we have to begin checking whether
  280.     the key/data pairs fit on their respective pages and because
  281.     we may need overflow pages for both the old and new pages
  282.  
  283.     The first page might be a page with regular key/data pairs
  284.     in which case we have a regular overflow condition and just
  285.     need to go on to the next page or it might be a big key/data 
  286.     pair in which case we need to fix the big key/data pair.
  287. */
  288. static int
  289. ugly_split( obucket, old_bufp, new_bufp, copyto, moved )
  290. u_int    obucket;    /* Same as __split_page */
  291. BUFHEAD    *old_bufp;        
  292. BUFHEAD    *new_bufp;
  293. u_short    copyto;        /* First byte on page which contains key/data values */
  294. int    moved;        /* number of pairs moved to new page */
  295. {
  296.     register BUFHEAD *bufp = old_bufp;        /* Buffer header for ino */
  297.     register u_short    *ino = (u_short *)old_bufp->page;    
  298.                         /* Page keys come off of */
  299.     register u_short    *np = (u_short *)new_bufp->page;    /* New page */
  300.     register u_short    *op = (u_short *)old_bufp->page;    
  301.                         /* Page keys go on to if they
  302.                            aren't moving */
  303.  
  304.     char    *cino;                /* Character value of ino */
  305.     BUFHEAD    *last_bfp = NULL;        /* Last buffer header OVFL which
  306.                            needs to be freed */
  307.     u_short    ov_addr, last_addr = 0;
  308.     u_short    n;
  309.     u_short    off;
  310.  
  311.     DBT    key, val;
  312.     SPLIT_RETURN    ret;
  313.  
  314.     n = ino[0]-1;
  315.     while ( n < ino[0] ) {
  316.     if ( ino[2] < REAL_KEY && ino[2] != OVFLPAGE ) {
  317.         if (__big_split (old_bufp, new_bufp, bufp, ov_addr, obucket, &ret)) {
  318.         return(-1);
  319.         }
  320.         old_bufp = ret.oldp;
  321.         if ( !old_bufp ) return(-1);
  322.         op = (u_short *)old_bufp->page;
  323.         new_bufp = ret.newp;
  324.         if ( !new_bufp ) return(-1);
  325.         np = (u_short *)new_bufp->page;
  326.         bufp = ret.nextp;
  327.         if ( !bufp ) return(0);
  328.         cino = (char *)bufp->page;
  329.         ino = (u_short *)cino;
  330.         last_bfp = ret.nextp;
  331.     } else if ( ino[n+1] == OVFLPAGE ) {
  332.         ov_addr = ino[n];
  333.         /* 
  334.         Fix up the old page -- the extra 2 are the fields which
  335.         contained the overflow information 
  336.         */
  337.         ino[0] -= (moved + 2);
  338.         FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0]+3);
  339.         OFFSET(ino) = copyto;
  340.  
  341.         bufp = __get_buf ( ov_addr, bufp, 0 );
  342.         if ( !bufp ) return(-1);
  343.  
  344.         ino = (u_short *)bufp->page;
  345.         n = 1;
  346.         copyto = hashp->BSIZE;
  347.         moved = 0;
  348.  
  349.         if ( last_bfp ) {
  350.         __free_ovflpage( last_bfp);
  351.         }
  352.         last_bfp = bufp;
  353.     } 
  354.     
  355.  
  356.     /* Move regular sized pairs of there are any */
  357.     off = hashp->BSIZE;
  358.     for ( n = 1; (n < ino[0]) && (ino[n+1] >= REAL_KEY); n += 2 ) {
  359.         cino = (char *)ino;
  360.         key.data = (u_char *)cino + ino[n]; 
  361.         key.size = off - ino[n];
  362.         val.data = (u_char *)cino + ino[n+1];
  363.         val.size = ino[n] - ino[n+1];
  364.         off = ino[n+1];
  365.  
  366.         if ( __call_hash ( key.data, key.size ) == obucket ) {
  367.         /* Keep on old page */
  368.         if (PAIRFITS(op,(&key),(&val))) putpair((char *)op, &key, &val);
  369.         else {
  370.             old_bufp = __add_ovflpage ( old_bufp );
  371.             if ( !old_bufp ) return(-1);
  372.             op = (u_short *)old_bufp->page;
  373.             putpair ((char *)op, &key, &val);
  374.         }
  375.         old_bufp->flags |= BUF_MOD;
  376.         } else {
  377.         /* Move to new page */
  378.         if (PAIRFITS(np,(&key),(&val))) putpair((char *)np, &key, &val);
  379.         else {
  380.             new_bufp = __add_ovflpage ( new_bufp );
  381.             if ( !new_bufp )return(-1);
  382.             np = (u_short *)new_bufp->page;
  383.             putpair ((char *)np, &key, &val);
  384.         } 
  385.         new_bufp->flags |= BUF_MOD;
  386.         }
  387.     }
  388.     }
  389.     if ( last_bfp ) {
  390.     __free_ovflpage(last_bfp);
  391.     }
  392.  
  393.     return (0);
  394. }
  395. /*
  396.     Add the given pair to the page
  397.     1 ==> failure
  398.     0 ==> OK
  399. */
  400. extern int
  401. __addel(bufp, key, val)
  402. BUFHEAD    *bufp;
  403. DBT    *key;
  404. DBT    *val;
  405. {
  406.     register u_short *bp = (u_short *)bufp->page;
  407.     register u_short *sop;
  408.     int    do_expand;
  409.  
  410.     do_expand = 0;
  411.     while ( bp[0] &&  (bp[bp[0]] < REAL_KEY) ) {
  412.     /* Exception case */
  413.     if ( bp[2] < REAL_KEY ) {
  414.         /* This is a big-keydata pair */
  415.         bufp = __add_ovflpage(bufp);
  416.         if ( !bufp ) {
  417.         return(-1);
  418.         }
  419.         bp = (u_short *)bufp->page;
  420.     } else {
  421.         /* Try to squeeze key on this page */
  422.         if ( FREESPACE(bp) > PAIRSIZE(key,val) ) {
  423.         squeeze_key ( bp, key, val );
  424.         return(0);
  425.         } else {
  426.         bufp = __get_buf ( bp[bp[0]-1], bufp, 0 );
  427.         if (!bufp) {
  428.             return(-1);
  429.         }
  430.         bp = (u_short *)bufp->page;
  431.         }
  432.     }
  433.     }
  434.  
  435.     if ( PAIRFITS(bp,key,val) ) putpair (bufp->page, key, val);
  436.     else {
  437.     do_expand = 1;
  438.     bufp = __add_ovflpage ( bufp );
  439.     if (!bufp)return(-1);
  440.     sop = (u_short *) bufp->page;
  441.  
  442.     if ( PAIRFITS(sop, key, val) ) putpair ( (char *)sop, key, val );
  443.     else if ( __big_insert ( bufp, key, val ) ) {
  444.         return(-1);
  445.     }
  446.     }
  447.     bufp->flags |= BUF_MOD;
  448.     /* 
  449.     If the average number of keys per bucket exceeds the fill factor,
  450.     expand the table
  451.     */
  452.     hashp->NKEYS++;
  453.     if (do_expand || 
  454.     (hashp->NKEYS / (hashp->MAX_BUCKET+1) > hashp->FFACTOR) ) {
  455.      return(__expand_table());
  456.     }
  457.     return(0);
  458. }
  459.  
  460. /*
  461.     returns a pointer, NULL on error
  462. */
  463. extern BUFHEAD *
  464. __add_ovflpage ( bufp )
  465. BUFHEAD    *bufp;
  466. {
  467.     register    u_short    *sp = (u_short *)bufp->page;
  468.  
  469.     u_short    ovfl_num;
  470.     u_short    ndx, newoff;
  471.     char    *op;
  472.     DBT    okey, oval;
  473. #ifdef DEBUG1
  474.     int    tmp1, tmp2;
  475. #endif
  476.  
  477.     bufp->flags |= BUF_MOD;
  478.     ovfl_num = overflow_page ();
  479. #ifdef DEBUG1
  480.     tmp1 = bufp->addr;
  481.     tmp2 = bufp->ovfl?bufp->ovfl->addr:0;
  482. #endif
  483.     if (!ovfl_num || !(bufp->ovfl = __get_buf ( ovfl_num, bufp, 1 ))) {
  484.     return(NULL);
  485.     }
  486.     bufp->ovfl->flags |= BUF_MOD;
  487. #ifdef DEBUG1
  488.     fprintf ( stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", tmp1, tmp2, 
  489.         bufp->ovfl->addr );
  490. #endif
  491.     ndx = sp[0];
  492.     /* 
  493.     Since a pair is allocated on a page only if there's room
  494.     to add an overflow page, we know that the OVFL information
  495.     will fit on the page
  496.     */
  497.     sp[ndx+4] = OFFSET(sp);
  498.     sp[ndx+3] = FREESPACE(sp) - OVFLSIZE;
  499.     sp[ndx+1] = ovfl_num;
  500.     sp[ndx+2] = OVFLPAGE;
  501.     sp[0] = ndx+2;
  502. #ifdef HASH_STATISTICS
  503.         hash_overflows++;
  504. #endif
  505.     return(bufp->ovfl);
  506. }
  507.  
  508. /*
  509.     0 indicates SUCCESS
  510.     -1 indicates FAILURE
  511. */
  512. extern    int
  513. __get_page ( p, bucket, is_bucket, is_disk, is_bitmap )
  514. char    *p;
  515. u_int    bucket;
  516. int    is_bucket;
  517. int    is_disk;
  518. int    is_bitmap;
  519. {
  520.     register int size;
  521.     register int fd;
  522.     register int page;
  523.     u_short    *bp;
  524.     int        rsize;
  525.  
  526.     fd = hashp->fp;
  527.     size = hashp->BSIZE;
  528.  
  529.     if ( (fd == -1) || !is_disk ) { 
  530.     PAGE_INIT(p);
  531.     return(0);
  532.     }
  533.  
  534.     if ( is_bucket) page = BUCKET_TO_PAGE (bucket);
  535.     else page = OADDR_TO_PAGE (bucket);
  536.     if ((lseek ( fd, page << hashp->BSHIFT, SEEK_SET ) == -1) || 
  537.     ((rsize = read ( fd, p, size )) == -1 )) {
  538.     return(-1);
  539.     } 
  540.     bp = (u_short *)p;
  541.     if ( !rsize ) {
  542.     bp[0] = 0;        /* We hit the EOF, so initialize a new page */
  543.     } else if ( rsize != size ) {
  544.     errno = EFTYPE;        
  545.     return(-1);
  546.     }
  547.     if (!bp[0]) {
  548.     PAGE_INIT(p);
  549.     } else if ( hashp->LORDER != BYTE_ORDER ) {
  550.     register int i;
  551.     register int max;
  552.  
  553.     if ( is_bitmap ) {
  554.         max = hashp->BSIZE >> 2;    /* divide by 4 */
  555.         for ( i=0; i < max; i++ ) {
  556.         BLSWAP(((long *)p)[i]);
  557.         }
  558.     } else {
  559.         BSSWAP(bp[0]);
  560.         max = bp[0] + 2;
  561.         for ( i=1; i <= max; i++ ) {
  562.         BSSWAP(bp[i]);
  563.         }
  564.     }
  565.     }
  566.     return (0);
  567. }
  568.  
  569. /* 
  570.     Write page p to disk
  571.     -1==>failure
  572.     0==> OK
  573. */
  574. extern int
  575. __put_page ( p, bucket, is_bucket, is_bitmap )
  576. char    *p;
  577. u_int    bucket;
  578. int    is_bucket;
  579. int    is_bitmap;
  580. {
  581.     register int size;
  582.     register int fd;
  583.     register int page;
  584.     int    wsize;
  585.  
  586.     size = hashp->BSIZE;
  587.     if ( (hashp->fp == -1) && open_temp() ) return (1);
  588.     fd = hashp->fp;
  589.  
  590.     if ( hashp->LORDER != BYTE_ORDER ) {
  591.     register int i;
  592.     register int max;
  593.  
  594.     if ( is_bitmap ) {
  595.         max = hashp->BSIZE >> 2;    /* divide by 4 */
  596.         for ( i=0; i < max; i++ ) {
  597.         BLSWAP(((long *)p)[i]);
  598.         }
  599.     } else {
  600.         max = ((u_short *)p)[0] + 2;
  601.         for ( i=0; i <= max; i++ ) {
  602.         BSSWAP(((u_short *)p)[i]);
  603.         }
  604.     }
  605.     }
  606.     if (is_bucket ) page = BUCKET_TO_PAGE (bucket);
  607.     else page = OADDR_TO_PAGE ( bucket );
  608.     if ((lseek ( fd, page << hashp->BSHIFT, SEEK_SET ) == -1) || 
  609.     ((wsize = write ( fd, p, size )) == -1 )) {
  610.     /* Errno is set */
  611.     return(-1);
  612.     }
  613.     if ( wsize != size ) {
  614.     errno = EFTYPE;    
  615.     return(-1);
  616.     }
  617.     return(0);
  618. }
  619. #define BYTE_MASK    ((1 << INT_BYTE_SHIFT) -1)
  620. /*
  621.     Initialize a new bitmap page.  Bitmap pages are left in memory
  622.     once they are read in.
  623. */
  624. extern u_long *
  625. __init_bitmap(pnum, nbits, ndx)
  626. u_short    pnum;
  627. int    nbits;
  628. int    ndx;
  629. {
  630.     u_long    *ip;
  631.     int        clearints;
  632.     int        clearbytes;
  633.  
  634.     if ( !(ip = (u_long *)malloc (hashp->BSIZE)) ) return (NULL);
  635.     hashp->nmaps++;
  636.     clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1;
  637.     clearbytes = clearints << INT_TO_BYTE;
  638.     memset ((char *)ip, 0, clearbytes );
  639.     memset ( ((char *) ip) + clearbytes, 0xFF, 
  640.         hashp->BSIZE-clearbytes );
  641.     ip[clearints-1] = ALL_SET << (nbits & BYTE_MASK);
  642.     SETBIT(ip, 0);
  643.     hashp->BITMAPS[ndx] = pnum;
  644.     hashp->mapp[ndx] = ip;
  645.     return(ip);
  646. }
  647. static int
  648. first_free ( map )
  649. u_long map;
  650. {
  651.     register u_long      mask;
  652.     register u_long      i;
  653.  
  654.     mask = 0x1;
  655.     for ( i=0; i < BITS_PER_MAP; i++ ) {
  656.     if ( !(mask & map) ) return(i);
  657.     mask = mask << 1;
  658.     }
  659.     return ( i );
  660. }
  661.  
  662. static u_short
  663. overflow_page ( )
  664. {
  665.     register    int max_free;
  666.     register    int splitnum;
  667.     register    u_long *freep;
  668.     register    int offset;
  669.     u_short    addr;
  670.     int        in_use_bits;
  671.     int        free_page, free_bit;
  672.     int        i, j, bit;
  673. #ifdef DEBUG2
  674.     int    tmp1, tmp2;
  675. #endif
  676.  
  677.     splitnum = __log2(hashp->MAX_BUCKET);
  678.     max_free = hashp->SPARES[splitnum];
  679.  
  680.     free_page = (max_free-1) >> (hashp->BSHIFT + BYTE_SHIFT);
  681.     free_bit  = (max_free-1) & ((hashp->BSIZE << BYTE_SHIFT) - 1);
  682.  
  683.     /* Look through all the free maps to find the first free block */
  684.     for ( i = 0; i <= free_page; i++ ) {
  685.     if (!(freep = (u_long *)hashp->mapp[i])  &&
  686.         !(freep = fetch_bitmap(i)) ) {
  687.         return ( NULL );
  688.     }
  689.     if ( i == free_page ) in_use_bits = free_bit;
  690.     else in_use_bits = (hashp->BSIZE << BYTE_SHIFT) -1;
  691.  
  692.     for (j = 0, bit = 0; bit <= in_use_bits; j++, bit += BITS_PER_MAP ) {
  693.          if ( freep[j] != ALL_SET ) goto found;
  694.     }
  695.     }
  696.     /* No Free Page Found */
  697.     hashp->SPARES[splitnum]++;
  698.     offset = hashp->SPARES[splitnum] - 
  699.          (splitnum ? hashp->SPARES[splitnum-1] : 0);
  700.  
  701.     /* Check if we need to allocate a new bitmap page */
  702.     if ( free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1 ) {
  703.     free_page++;
  704. #define    OVMSG    "hash: out of overflow pages; increase page size\n"
  705.     if ( free_page >= NCACHED ) {
  706.         (void) write (STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
  707.         return(NULL);
  708.     }
  709.     /* 
  710.         This is tricky.  The 1 indicates that you want the
  711.         new page allocated with 1 clear bit.  Actually, you
  712.         are going to allocate 2 pages from this map.  The first
  713.         is going to be the map page, the second is the overflow
  714.         page we were looking for.  The init_bitmap routine
  715.         automatically, sets the first bit of itself to indicate
  716.         that the bitmap itself is in use.  We would explicitly
  717.         set the second bit, but don't have to if we tell init_bitmap
  718.         not to leave it clear in the first place.
  719.     */
  720.     __init_bitmap ( OADDR_OF(splitnum, offset), 1, free_page );
  721.     hashp->SPARES[splitnum]++;
  722. #ifdef DEBUG2
  723.     free_bit = 2;
  724. #endif
  725.     offset++;
  726.     } else {
  727.     /* 
  728.         Free_bit addresses the last used bit.  Bump it to
  729.         address the first available bit.
  730.     */    
  731.     free_bit++;
  732.     SETBIT ( freep, free_bit );
  733.     }
  734.  
  735.     /* Calculate address of the new overflow page */
  736.     if ( offset > SPLITMASK ) {
  737.     (void) write (STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
  738.     return(NULL);
  739.     }
  740.     addr = OADDR_OF(splitnum, offset);
  741. #ifdef DEBUG2
  742.     fprintf ( stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
  743.         addr, free_bit, free_page );
  744. #endif
  745.     return(addr);
  746.  
  747. found:
  748.     bit = bit + first_free(freep[j]);
  749.     SETBIT(freep,bit);
  750. #ifdef DEBUG2
  751.     tmp1 = bit;
  752.     tmp2 = i;
  753. #endif
  754.     /* 
  755.     Bits are addressed starting with 0, but overflow pages are
  756.     addressed beginning at 1. Bit is a bit addressnumber, so we 
  757.     need to increment it to convert it to a page number.
  758.     */
  759.     bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT));
  760.  
  761.     /* Calculate the split number for this page */
  762.     for ( i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++ );
  763.     offset =(i ? bit - hashp->SPARES[i-1] : bit );
  764.     if ( offset >= SPLITMASK ) return(NULL);/* Out of overflow pages */
  765.     addr = OADDR_OF(i, offset);
  766. #ifdef DEBUG2
  767.     fprintf ( stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
  768.         addr, tmp1, tmp2 );
  769. #endif
  770.  
  771.     /* Allocate and return the overflow page */
  772.     return (addr);
  773. }
  774.  
  775. /*
  776.     Mark this overflow page as free.
  777. */
  778. __free_ovflpage ( obufp )
  779. BUFHEAD    *obufp;
  780. {
  781.     register u_short addr = obufp->addr;
  782.     int    free_page, free_bit;
  783.     int bit_address;
  784.     u_short ndx;
  785.     u_long *freep;
  786.     int j;
  787.  
  788. #ifdef DEBUG1
  789.     fprintf ( stderr, "Freeing %d\n", addr );
  790. #endif
  791.     ndx = (((u_short)addr) >> SPLITSHIFT);
  792.     bit_address = (ndx ? hashp->SPARES[ndx-1] : 0) + (addr & SPLITMASK) - 1;
  793.     free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT));
  794.     free_bit  = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1);
  795.  
  796.     if ( !(freep = hashp->mapp[free_page]) &&
  797.      !(freep = fetch_bitmap( free_page )) ) {
  798.     /* 
  799.         This had better never happen.  It means we tried to
  800.         read a bitmap that has already had overflow pages allocated
  801.         off it, and we failed to read it from the file
  802.     */
  803.     assert(0);
  804.     }
  805.     CLRBIT(freep, free_bit);
  806. #ifdef DEBUG2
  807.     fprintf ( stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
  808.         obufp->addr, free_bit, free_page );
  809. #endif
  810.     __reclaim_buf ( obufp );
  811.     return;
  812. }
  813.  
  814. /*
  815. 0 success
  816. -1 failure
  817. */
  818. static int
  819. open_temp()
  820. {
  821.     sigset_t    set, oset;
  822.     static char    namestr[] = "_hashXXXXXX";
  823.  
  824.     /* Block signals; make sure file goes away at process exit. */
  825.     sigemptyset(&set);
  826.     sigaddset(&set, SIGHUP);
  827.     sigaddset(&set, SIGINT);
  828.     sigaddset(&set, SIGQUIT);
  829.     sigaddset(&set, SIGTERM);
  830.     (void)sigprocmask(SIG_BLOCK, &set, &oset);
  831.     if ((hashp->fp = mkstemp ( namestr )) != -1) {
  832.     (void)unlink(namestr);
  833.     (void)fcntl(hashp->fp, F_SETFD, 1);
  834.     }
  835.     (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL);
  836.     return(hashp->fp != -1 ? 0 : -1);
  837. }
  838.  
  839. /* 
  840.     We have to know that the key will fit, but the
  841.     last entry on the page is an overflow pair, so we
  842.     need to shift things.
  843. */
  844. static void
  845. squeeze_key ( sp, key, val )
  846. u_short    *sp;
  847. DBT    *key;
  848. DBT    *val;
  849. {
  850.     register    char    *p = (char *)sp;
  851.     u_short    free_space, off;
  852.     u_short    pageno, n;
  853.  
  854.     n = sp[0];
  855.     free_space = FREESPACE(sp);
  856.     off = OFFSET(sp);
  857.  
  858.     pageno = sp[n-1];
  859.     off -= key->size;
  860.     sp[n-1] = off;
  861.     bcopy ( key->data, p + off, key->size );
  862.     off -= val->size;
  863.     sp[n] = off;
  864.     bcopy ( val->data, p + off, val->size );
  865.     sp[0] = n+2;
  866.     sp[n+1] = pageno;
  867.     sp[n+2] = OVFLPAGE;
  868.     FREESPACE(sp) = free_space - PAIRSIZE(key,val);
  869.     OFFSET(sp) = off;
  870. }
  871.  
  872. static u_long *
  873. fetch_bitmap ( ndx ) 
  874. int    ndx;
  875. {
  876.     if ( ndx >= hashp->nmaps  ||
  877.     !(hashp->mapp[ndx] = (u_long *)malloc ( hashp->BSIZE )) ||
  878.      __get_page ((char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) {
  879.  
  880.         return(NULL);
  881.     }
  882.     return ( hashp->mapp[ndx] );
  883. }
  884. #ifdef DEBUG4
  885. print_chain ( addr )
  886. short    addr;
  887. {
  888.     BUFHEAD    *bufp;
  889.     short    *bp;
  890.     short    oaddr;
  891.  
  892.     fprintf ( stderr, "%d ", addr );
  893.     bufp = __get_buf ( (int)addr, NULL, 0 );
  894.     bp = (short *)bufp->page;
  895.     while ( bp[0] && 
  896.         ((bp[bp[0]] == OVFLPAGE) ||
  897.          ((bp[0] > 2) && bp[2] < REAL_KEY))) {
  898.         oaddr = bp[bp[0]-1];
  899.         fprintf ( stderr, "%d ", (int)oaddr );
  900.         bufp = __get_buf ( (int)oaddr, bufp, 0 );
  901.         bp = (short *)bufp->page;
  902.     }
  903.     fprintf ( stderr, "\n" );
  904. }
  905. #endif
  906.